f_{i, j, 0} =\max \left\{f_{i-1, j-1,0}, f_{i-1, j-1,1}, f_{i-1, j-1,2}\right\}+d_{x_{i}, y_{j}}

f_{i, j, 1} =\max \left\{f_{i, j-1,1}-b, f_{i, j-1,0}-a, f_{i, j-1,2}-a\right\}

f_{i, j, 2} =\max \left\{f_{i-1, j, 2}-b, f_{i-1, j, 0}-a, f_{i-1, j, 1}-a\right\}

初始化从后往前扫[0][i][1] [i][0][2]

给其他赋值-INF

初始化很重要！！！

#include <bits/stdc++.h>
#define INF 0x3f3f3f3f
#define N 3020
using namespace std;

char a[N], b[N];
int numa, numb;
int d[5][5];
int dp[N][N][5];
char check[30];
int cost(int x, int y)
{
    return d[check[a[x] - 'A']][check[b[y] - 'A']];
}

int main()
{
    check['A' - 'A'] = 0, check['T' - 'A'] = 1, check['G' - 'A'] = 2, check['C' - 'A'] = 3;
    scanf("%s", a + 1);
    scanf("%s", b + 1);
    for (int i = 0; i < 4; i++)
        for (int j = 0; j < 4; j++)
            scanf("%d", &d[i][j]);
    scanf("%d%d", &numa, &numb);
    for (int i = max(strlen(a + 1), strlen(b + 1)); i > 0; --i)
    {
        dp[0][i][0] = dp[i][0][0] = dp[0][i][2] = dp[i][0][1] = -INF;
        dp[0][i][1] = dp[i][0][2] = -numa - numb * (i - 1);
    }
    dp[0][0][1] = dp[0][0][2] = -INF;

    for (int i = 1; i <= strlen(a + 1); i++)
        for (int j = 1; j <= strlen(b + 1); j++)
            for (int k = 0; k < 3; k++)
            {
                if (k == 0)
                    dp[i][j][0] = max(dp[i - 1][j - 1][0], max(dp[i - 1][j - 1][1], dp[i - 1][j - 1][2])) + cost(i, j);
                if (k == 1)
                    dp[i][j][1] = max(dp[i][j - 1][1] - numb, max(dp[i][j - 1][2] - numa, dp[i][j - 1][0] - numa));
                if (k == 2)
                    dp[i][j][2] = max(dp[i - 1][j][1] - numa, max(dp[i - 1][j][2] - numb, dp[i - 1][j][0] - numa));
            }
    int ans = -INF;
    for (int i = 0; i < 3; i++)
        ans = max(ans, dp[strlen(a + 1)][strlen(b + 1)][i]);
    cout << ans << endl;
}

一小组检查自己的好数据

GGAT
ATCC
5 -4 -4 -4 
-4 5 -4 -4 
-4 -4 5 -4 
-4 -4 -4 5 
2 1